자료구조(Data Structure)
Stack: 가장 최근에 들어온 데이터 우선 삭제
Queue: 가장 먼저 들어온 데이터 우선 삭제
Priority Queue: 우선순위가 높은 데이터 우선 삭제
우선순위 큐를 구현할 때,
배열, 연결리스트, 힙등의 자료 구조로 구현
Heap
완전 이진 트리의 일종으로 우선순위 큐를 위한 자료구조(반정렬 상태를 유지한다.)
- 최대 힙 ; A[parent(i)]>=A[i] 일반적으로 힙정렬 알고리즘에서 사용
- 최소 힙 ; A[parent(i)]<=A[i] 일반적으로 우선순위 큐를 구현할 때 사용
높이: lg(n)
#include <iostream>
using namespace std;
template <typename T>
struct Heap{
T* arr;
int heap_size;
Heap(T* _arr, int _heap_size): arr(_arr), heap_size(_heap_size){}
T operator [](int ind){
assert(ind-1>=0 && ind-1<=heap_size);
return arr[ind-1];
}
void swap(int i, int j){
i--; j--;
T tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
void print(void){
for(int i=0; i<heap_size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[heap_size-1]<<endl;
}
};
// index start with 1
int parent(int i){
return i/2;
}
int left(int i){
return i<<1;
}
int right(int i){
return (i<<1)+1;
}
// O(lgn)
template <typename T>
void Max_Heapify(Heap<T>& heap, int i){
int l=left(i), r=right(i), largest;
if(l<=heap.heap_size && heap[l]>heap[i]) largest=l;
else largest=i;
if(r<=heap.heap_size && heap[r]>heap[largest]) largest=r;
if(largest!=i){
heap.swap(i, largest);
Max_Heapify(heap, largest);
}
}
// O(n x lgn)
template <typename T>
Heap<T> Build_Max_Heap(int* arr, int size){
Heap<T> heap(arr, size);
for(int i=size/2; i>=1; --i) Max_Heapify<T>(heap, i);
return heap;
}
int main(void){
int arr[]={4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
int size=sizeof(arr)/sizeof(int);
Heap heap=Build_Max_Heap<int>(arr, size);
heap.print();
return 0;
}
Build Max Heap & Build Min Heap:
정렬되지 않은 입력 배열로부터 최대 힙을 만든다. O(n) 선형시간에 처리 가능
Heap Sort
#include <iostream>
using namespace std;
template <typename T>
struct Heap{
T* arr;
int heap_size;
Heap(T* _arr, int _heap_size): arr(_arr), heap_size(_heap_size){}
T operator [](int ind){
assert(ind-1>=0 && ind-1<=heap_size);
return arr[ind-1];
}
void swap(int i, int j){
i--; j--;
T tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
void print(void){
for(int i=0; i<heap_size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[heap_size-1]<<endl;
}
};
// index start with 1
int parent(int i){
return i/2;
}
int left(int i){
return i<<1;
}
int right(int i){
return (i<<1)+1;
}
// O(lgn)
template <typename T>
void Max_Heapify(Heap<T>& heap, int i){
int l=left(i), r=right(i), largest;
if(l<=heap.heap_size && heap[l]>heap[i]) largest=l;
else largest=i;
if(r<=heap.heap_size && heap[r]>heap[largest]) largest=r;
if(largest!=i){
heap.swap(i, largest);
Max_Heapify(heap, largest);
}
}
// O(n x lgn)
template <typename T>
Heap<T> Build_Max_Heap(int* arr, int size){
Heap<T> heap(arr, size);
for(int i=size/2; i>=1; --i) Max_Heapify<T>(heap, i);
return heap;
}
// O(n x lgn)
template <typename T>
Heap<T> HeapSort(int* arr, int size){
Heap<T> heap=Build_Max_Heap<T>(arr, size);
for(int i=size; i>=2; --i){
heap.swap(1, i);
heap.heap_size--;
Max_Heapify<T>(heap, 1);
}
heap.heap_size=size;
return heap;
}
int main(void){
int arr[]={4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
int size=sizeof(arr)/sizeof(int);
Heap<int> heap=HeapSort<int>(arr, size);
heap.print();
return 0;
}
Priority Queue with Heap
우선순위 큐: 키 값을 가진 원소들의 집합 S를 다루기 위한 자료구조
최대 우선 순위 큐 (스케줄러 등에서 사용)
- Insert(S, x): S에 원소 x를 새로 넣는다.
- Maximum(S): 키 값이 최대인 원소를 리턴
- Extract_Max(S): S에서 키 값이 최대인 원소를 제거
- Increase-Key(S, x, k): 원소 x의 키값을 k로 증가시킨다.
#include <iostream>
#include <climits>
#include <cstdio>
using namespace std;
template <typename T>
class PriorityQueue{
public:
int parent(int ind){
return ind>>1;
}
int left(int ind){
return ind<<1;
}
int right(int ind){
return (ind<<1)+1;
}
T* array(void){
return arr;
}
void swap(int i, int j){
i--; j--;
assert(i>=0 && j>=0);
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
void MaxHeapify(int ind){
int l=left(ind), r=right(ind), largest;
assert(ind>=0 && l>=0 && r>=0);
if(l<=this->heap_size && this->arr[l-1]>this->arr[ind-1]) largest=l;
else largest=ind;
if(r<=this->heap_size && this->arr[r-1]>this->arr[largest-1]) largest=r;
if(largest!=ind){
swap(ind, largest);
MaxHeapify(largest);
}
}
void Build_Max_Heap(void){
for(int i=this->heap_size/2; i>=1; --i){
MaxHeapify(i);
}
}
void HeapSort(void){
Build_Max_Heap();
int prev_size=this->heap_size;
for(int i=this->heap_size; i>=2; --i){
swap(1, i);
this->heap_size--;
MaxHeapify(1);
}
this->heap_size=prev_size;
}
T Heap_MaxiMum(void){
return this->arr[0];
}
T Heap_Extract_Max(void){
if(this->heap_size<1){
perror("Heap Underflow");
exit(1);
}
T max=arr[0];
arr[0]=arr[heap_size-1];
T* arr2=new T[heap_size-1];
heap_size--;
for(int i=0; i<heap_size; ++i){
arr2[i]=arr[i];
}
delete arr;
arr=arr2;
MaxHeapify(1);
return max;
}
void Heap_Increase_Key(int i, T key){
if(key<arr[i-1]){
perror("New key is smaller then present one.");
exit(1);
}
arr[i-1]=key;
while(i>1 && arr[parent(i)-1]<arr[i-1]){
swap(i, parent(i));
i=parent(i);
}
}
void Max_Heap_Insert(T key){
T* arr2=new T[this->heap_size+1];
for(int i=0; i<this->heap_size; ++i) arr2[i]=arr[i];
delete arr;
arr=arr2;
this->heap_size++;
arr[heap_size-1]=-INT_MAX;
Heap_Increase_Key(heap_size, key);
}
void print(void){
for(int i=0; i<heap_size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[heap_size-1]<<endl;
}
PriorityQueue(T* _arr, int _heap_size): heap_size(_heap_size){
arr=new T[heap_size];
for(int i=0; i<heap_size; ++i) arr[i]=_arr[i];
Build_Max_Heap();
}
~PriorityQueue(){
delete arr;
}
private:
T* arr;
int heap_size;
};
int main(void){
int arr[]={15, 13, 9, 5, 12, 8, 7, 4, 0 ,6, 2, 1};
int size=sizeof(arr)/sizeof(int);
PriorityQueue<int>* pqueue=new PriorityQueue<int>(arr, size);
cout<<"Max: "<<pqueue->Heap_Extract_Max()<<endl;
pqueue->print();
pqueue->Heap_Increase_Key(5, 30);
cout<<"increase key i=5, key=30\n";
pqueue->print();
cout<<"insert key key=15\n";
pqueue->Max_Heap_Insert(15);
pqueue->print();
cout<<"sort Queue\n";
pqueue->HeapSort();
pqueue->print();
delete pqueue;
}